﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol215
{
    public void swap(ref int x, ref int y)
    {
        int temp = x; x = y; y = temp;

    }
    //另一种swap
    private static void Swap1(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


    public void makeBigHeap(int[] nums, int len)
    {


        for (int i = len / 2; i >= 0; i--)
        { //只遍历一半，也就是所有的分支节点

            adjustHeap(nums, i, len);

        }

    }
    public void adjustHeap(int[] nums, int i, int len)
    {
        int left = 2 * i + 1;//也有可能没有孩子

        int right = 2 * i + 2;
        int larger = i;
        if (left < len && nums[larger] < nums[left])
        {

            larger = left;

        }

        if (right < len && nums[larger] < nums[right])
        {

            larger = right;


        }

        if (larger != i)//只有调整过才执行，不然无限循环了
        {
            Swap1(nums,i,larger);
            adjustHeap(nums, larger, len);//调整新生成的（新的堆，小元素下坠）  
        }


    }
    public int FindKthLargest2(int[] nums, int k)//大根堆法
    {
        int len = nums.Length;
        //先构建一个大根堆
        makeBigHeap(nums, len);//这个大根堆只有最上面的最大
        Console.WriteLine(nums[0]);

        for (int i = nums.Length - 1; i >= 0; i--)//遍历所有的会超时
        {
            Console.WriteLine(nums[0]);
            swap(ref nums[i], ref nums[0]);
            
            //交换之后调整一下就行，不用重构
            len--;
            //solHeap.adjustHeap(nums, 0, len);
            makeBigHeap(nums, len);

        }

        return nums[nums.Length - k];


        //for (int i = nums.Length - 1; i >= nums.Length - k; i--)//遍历所有的会超时
        //{
        //    swap(ref nums[i], ref nums[0]);
        //    //交换之后调整一下就行，不用重构
        //    len--;
        //    //solHeap.adjustHeap(nums, 0, len);
        //    makeBigHeap(nums, len);

        //}

        //return nums[nums.Length - k];



    }



    public int FindKthLargest(int[] nums, int k)//使用快排，但是记得排到k的位置就可以停止了
    {

        QuickSort(nums, 0, nums.Length - 1, k) ;
        return nums[nums.Length - k];
    }
    public void swap(int[] nums, int x, int y)
    {
        int swap = nums[x];
        nums[x] = nums[y];
        nums[y] = swap;
    }
    public void QuickSort(int[] nums, int left, int right,int k)
    {
        if (left < right)//递归终止的条件，返回上一层
        {
            //排序一次
            int pivotIndex = Partition(nums, left, right);

            if(pivotIndex ==(nums.Length - k))
            {//说明位置已经正确,不要继续递归了
                return;
            }

            //不要一起递归，只递归一边
            if (pivotIndex < (nums.Length - k))
            {
                //递归右边
                Partition(nums, pivotIndex + 1, right);
            }
            else
            {
                Partition(nums, left, pivotIndex - 1);//这里的left没变
            }
          
          

        }
    }

    private int Partition(int[] nums, int left, int right)
    {
        int val = nums[left];//基准值
        while (left < right)
        {
            //先移动右边的
            while (nums[right] > val)
            {
                right--;
            }


            while (nums[left] < val)
            {
                left++;

            }

            swap(nums, left, right);
        }
        return left;//返回left和right一样，right=left=pivot分界线
    }

}
public class Solution215_2
{
    public int FindKthLargest(int[] nums, int k)
    {

        int target = nums.Length - k;
        //第k大，就是排序之后的第target个数字，也就是piviot指向的index
        QuickSort(nums, 0, nums.Length - 1, target);
        Console.WriteLine(target);

        //输出数组


        for (int i = 0; i < nums.Length; i++)
        {
            Console.Write(nums[i]+",");

        }

        Console.WriteLine();


        return nums[target];

    }

    public void QuickSort(int[] nums, int left, int right, int target)
    {
        if (left < right)//递归终止的条件，返回上一层
        {
            //排序一次
            int pivotIndex = Partition(nums, left, right);

            if (pivotIndex == target)
            {//说明位置已经正确,不要继续递归了
                return;
            }

            //不要一起递归，只递归一边
            if (pivotIndex < target)//说明在右边
            {
                //递归右边
                QuickSort(nums, pivotIndex+1 , right, target);
            }
            else
            {
                QuickSort(nums, left, pivotIndex-1, target);//这里的left没变
            }



        }
    }


    int Partition(int[] nums, int start, int end)//随机选择中间的数字
    {


        Console.WriteLine(start);

        int left = start;
        int right = end;
        
        int val = nums[left];

        while (left < right)
        {
            while (left < right && nums[right] >= val)//找到是比他严格小的
            {

                right--;
            }
            nums[left] = nums[right];

            while (left < right && nums[left] <= val)
            {

                left++;
            }
            nums[right] = nums[left];

        }
        nums[left] = val;
        return left;



    }
    static void Swap(int[] nums, int i, int j)
    {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
class Program215
{

    static void Main()
    {
        Solution215_2 s = new ();
        int[] nums = [7, 6, 5, 4, 3, 2, 1];
       int res= s.FindKthLargest(nums, 2);

        Console.WriteLine(res);
        Console.ReadKey();

    }
}